#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      Administrator
#
# Created:     20\04\2020
# Copyright:   (c) Administrator 2020
# Licence:     <your licence>
#-------------------------------------------------------------------------------
import numpy as np
import random
import copy
import matplotlib.pyplot as plt

#生成种群
group = []

#适应度
fitnessList = []

#仓库编号数量 固定
maxNumber = 6 * 12
#每个拣货员订单的大小 可变
orderSize = 10
#与编号的对应要 加 1 因为这个是从0 开始的索引
numberMap = []
#从货架上取货的时间 秒 这个不用计算 其实是根据订单的长度而固定了
takeTimePerGood = 10
takeTimePerOrder = takeTimePerGood * orderSize
L1 = 2;
L2 = 3;
L3 = 4;
#1米每秒
v = 1
#每一轮的平均时间
averageTime = []
#每一轮的最小时间
minTime = []
#每一轮最小时间对应的 订单
minOrder = []
#交叉概率
crossProbability = 0.3
#变异概率
mutationProbability = 0.1

#根据两个订单生成一个染色体
def createOne(twoOrder):
    newOrder = copy.copy(twoOrder)
    random.shuffle(newOrder[0])
    random.shuffle(newOrder[1])
    return newOrder

#生成初始的种群
#groupSize 初始种群个数
def initialize(groupSize):
    #一个染色体 两个订单 用两个数组表示
    order1 = random.sample(range(1,maxNumber+1),orderSize)
    order2 = random.sample(range(1,maxNumber+1),orderSize)
    #根据两个订单生成 初始种群*
    for i in range(groupSize):
        group.append(createOne([copy.copy(order1),copy.copy(order2)]))


def createMap():
    x = []
    for i in range(1,7):
    	y = [(i,z) for z in range(1,13)]
    	x = x + y
    return x

#把编号变成表示
# 1订单对应的是 numberMap的0位置
def numberToPosition(number):
    return numberMap[number-1]


#适应性计算 直接算出每个订单的时间值
def fitness():
    global averageTime
    #要算出 一个订单的任意两个点之间的等待时间 如此才能跟另外一个 拣货员去比较
    #计算每一个订单需要的时间
    timeArr = []
    for i in range(len(group)):
        timeArr.append(fitnessSingle(group[i]))

    averageTime.append(sum(timeArr) / len(group))
    timeArr = np.array(timeArr)
    #因为这里是求最小值 所以适度函数要是时间的倒数
    timeArr = 1/(timeArr + 1)
    return timeArr

#返回所用时间
def fitnessSingle(chromosome):
    #好像只能一个一个的去计算了 因为后面的等待时间跟前面的是相关的，所以必须算出前面的等待时间 才知道后面的等待时间
    #核心在于计算等待时间
    #方案： 先把A B 的点的每个时间取货时间点按照时间线的顺序排列 然后搜索这一个列 如果出现了 A B  这样的现象 且 AB在同一个巷道  那么就是B在等待A B在这段时间什么也没做 时间点往后移动  后面的时间重新排列

    positionA = [numberToPosition(x) for x in chromosome[0]]
    positionB = [numberToPosition(x) for x in chromosome[1]]
    #这个要比点要多一个 因为有出口和入口   这个distance是两两相邻的距离
    distanceA = [distance(x,positionA) for x in range(orderSize+1) ]
    distanceB = [distance(x,positionB) for x in range(orderSize+1) ]
    timeLineA = []
    timeLineB = []
    tmpTotal = 0
    for i in range(orderSize + 1):
        #距离 除以速度
        tmpTotal = tmpTotal + distanceA[i]
        time = tmpTotal/v + i * takeTimePerGood
        timeLineA.append(time)

    tmpTotal = 0
    for i in range(orderSize + 1):
        #距离 除以速度
        tmpTotal = tmpTotal + distanceB[i]
        time = tmpTotal/v + i * takeTimePerGood
        timeLineB.append(time)

    #遍历时间线看看有没有AB在同一个巷子 而导致等待时间的 从AB 相邻的两个时间点判断是否有共用一个巷子  然后把B 挪到A下一个A出巷的 那个点 B后面的序列的时间都加上一个时间的断 就是 A 到这出巷的时间 + 一个取货的时间 （好像加不加都行-主要看这个模型的假设了）
    j = 0
    k = 0
    isOut = False
    while j < orderSize and k < orderSize:
        if(isOut):
            break
        #print(j)
        #print(k)
        #从A 和 B的对列中各取一个  比较时间 找到时间相邻的两个点，然后判断这两个人的巷子是否一样 如果一样 那么就可以挪后面那个人的 时间线了 如果不一样
        if(timeLineA[j] < timeLineB[k]):
            if(timeLineA[j+1] < timeLineB[k]):
                j = j + 1
            else:
                #相邻了， 检查是否在同一个巷子
                #同一个巷子
                if(positionA[j][0] == positionB[k][0]):
                    #移动后进入巷子的哥们
                    #找到目标时间点
                    l = j
                    while(True):
                        if( l+1 == orderSize ):
                            isOut = True
                            break
                        if(positionA[l+1][0] == positionA[j][0]):
                            l = l+1
                        else:
                            l = j+1 #移动到下一不在这条巷子的位置
                            break
                    if(isOut):
                        break
                    diffTime = timeLineA[l] - timeLineA[j]
                    #另外一条移动时间线
                    for z in range(k,orderSize+1):
                        timeLineB[z] = timeLineB[z] + diffTime
                    #A的时间移动到 l位置开始
                    j = l
                else:
                    j = j + 1

        elif(timeLineA[j] > timeLineB[k]):
            if(timeLineA[j] > timeLineB[k+1] ):
                k = k + 1
            else:
                if(positionA[j][0] == positionB[k][0]):
                    #移动后进入巷子的哥们
                    #找到目标时间点
                    l = k
                    while(True):
                        if( l+1 == orderSize ):
                            isOut = True
                            break
                        if(positionB[l+1][0] == positionB[k][0]):
                            l = l+1
                        else:
                            l = k+1 #移动到下一不在这条巷子的位置
                            break
                    if(isOut):
                        break
                    diffTime = timeLineB[l] - timeLineB[k]
                    #另外一条移动时间线
                    for z in range(j,orderSize+1):
                        timeLineA[z] = timeLineA[z] + diffTime
                    #A的时间移动到 l位置开始
                    k = l
                else:
                    k = k + 1

        elif(timeLineA[j] == timeLineB[k]):
            #随便选一个在前面 然后比较是不是在同一个巷子 就默认第一个
            #同一个巷子
            if(positionA[j][0] == positionB[k][0]):
                #移动后进入巷子的哥们
                #找到目标时间点
                l = j
                while(True):
                    if( l+1 == orderSize ):
                        isOut = True
                        break
                    if(positionA[l+1][0] == positionA[j][0]):
                        l = l+1
                    else:
                        l = j+1 #移动到下一不在这条巷子的位置
                        break
                if(isOut):
                    break
                diffTime = timeLineA[l] - timeLineA[j]
                #另外一条移动时间线
                for z in range(k,orderSize+1):
                    timeLineB[z] = timeLineB[z] + diffTime
                #A的时间移动到 l位置开始
                j = l
            #如果不是同一个巷子 两个游标都往前一步
            else:
                j = j + 1
                k = k + 1

        if j == orderSize or k == orderSize:
            break


    #检查哪一个时间线最大 就用谁的时间作为染色体的时间
    thisTime = max(timeLineA[orderSize],timeLineB[orderSize])

    return thisTime



def distance(index,positionArr):
    d = 0
    if(index == 0):
        #计算从出口到第一个点的距离
        d = positionArr[index][1] * L1 + (positionArr[index][0]-1)*(L3 + 2*L2)
    elif(index > 0 and index < orderSize):
        #在同一条巷道上
        if(positionArr[index][0] == positionArr[index-1][0]):
            d = abs(positionArr[index][1] - positionArr[index-1][1]) * L1
        else:
            if(positionArr[index][1] <= 6 and positionArr[index][1] >= 1 and positionArr[index-1][1] <= 6 and positionArr[index-1][1] >= 1):
                d = (positionArr[index][1] + positionArr[index-1][1]) * L1 + abs(positionArr[index][0] - positionArr[index][0])*(L3 + 2* L2)
            elif(positionArr[index][1] <= 12 and positionArr[index][1] >= 7 and positionArr[index-1][1] <= 12 and positionArr[index-1][1] >= 7):
                d = (abs(12 - positionArr[index][1]) + abs(12 - positionArr[index-1][1])) * L1 + abs(positionArr[index][0] - positionArr[index][0])*(L3 + 2* L2)
            else:
                tmp1 = (positionArr[index][1] + positionArr[index-1][1]) * L1 + abs(positionArr[index][0] - positionArr[index][0])*(L3 + 2* L2)
                tmp2 = (24 - positionArr[index][1] - positionArr[index][1]) * L1 + abs(positionArr[index][0] - positionArr[index][0])*(L3 + 2* L2)
                d = min(tmp1,tmp2)
    elif(index == orderSize):
        #这个是最后到出口的
        d = positionArr[index-1][1] * L1 + (positionArr[index-1][0]-1)*(L3 + 2*L2)
    return d




#选择算子 返回选择后的编号  轮盘方法
def select(fitnessArr):
    probability = []
    total = sum(fitnessArr)
    tmp = 0
    for s in range(len(fitnessArr)):
        tmp = fitnessArr[s] + tmp
        probability.append(tmp / total)
    randoms = np.random.uniform(0,1,len(group))
    selectors = []
    for s in randoms:
        for z in range(len(probability)):
            if(probability[z] > s):
                selectors.append(z)
                break
    return selectors

#交叉算子
def crossover(selectors):
    global group
    #print(group)
    #根据选择算子 选择
    newGroup = []
    for s in selectors:
        newGroup.append(group[s])
    group = newGroup
    #print(group)
    #不能每一个都交叉 是按照概率交叉
    #按照指定的交叉概率  生成种子

    seeds = (len(group)//2)*crossProbability
    seeds = int(seeds)
    seeds = [1] * seeds
    seeds = seeds + [0]*(len(group)//2 - len(seeds))
    random.shuffle(seeds)

    #跟染色体配对
    a = random.sample(range(len(group)//2),len(group)//2)
    b = random.sample(range(len(group)//2,len(group)),len(group)//2)

    #真对每一个计算交叉点
    crosspoint = np.random.randint(0,orderSize*2,len(group)//2)
    #print(group)
    #len(group)/2 对染色体
    for s in range(len(a)):
        if seeds[s] == 0:
            continue
        if(crosspoint[s] <= orderSize):
            tmp = group[a[s]][0][0:crosspoint[s]]
            group[a[s]][0][0:crosspoint[s]] = group[b[s]][0][0:crosspoint[s]]
            group[b[s]][0][0:crosspoint[s]] = tmp
        elif(crosspoint[s] > orderSize):
            tmp = group[a[s]][1][crosspoint[s]-orderSize:orderSize]
            group[a[s]][1][crosspoint[s]-orderSize:orderSize] = group[b[s]][1][crosspoint[s]-orderSize:orderSize]
            group[b[s]][1][crosspoint[s]-orderSize:orderSize] = tmp

    #print(group)
    #交叉点之后的 交换
    pass

#变异算子
def mutation():
    #交叉算子可以把两个订单合并一个染色体来看待 但是变异就不行了  因为订单内的单必须在订单列表内交换
    randomA1 = np.random.randint(0,orderSize,len(group))
    randomA2 = np.random.randint(0,orderSize,len(group))
    randomB1 = np.random.randint(0,orderSize,len(group))
    randomB2 = np.random.randint(0,orderSize,len(group))

    #变异概率
    seeds = len(group)*mutationProbability
    seeds = int(seeds)
    #有的1变成2 变成2的就是 拣货员B变异  1,2的随机列表
    seeds = np.random.randint(1,3,seeds)
    seeds = seeds.tolist() + [0]*(len(group) - len(seeds))
    random.shuffle(seeds)

    for s in range(len(group)):
        if(seeds[s] == 0):
            continue
        if(seeds[s] == 1):
            tmp = group[s][0][randomA1[s]]
            group[s][0][randomA1[s]] = group[s][0][randomA2[s]]
            group[s][0][randomA2[s]] = tmp
        if(seeds[s] == 2):
            tmp = group[s][1][randomB1[s]]
            group[s][1][randomB1[s]] = group[s][1][randomB2[s]]
            group[s][1][randomB2[s]] = tmp


def main():
    global numberMap
    #遗传代数
    generation = 100
    initialize(40)
    numberMap = createMap()
    for i in range(generation):
        fitnessArr =  fitness()
        #plt.pie(fitnessArr*100) 可以用这个来看不同的代数其个体之间的差距
        #plt.show()
        #print(fitnessArr)
        selectors = select(fitnessArr)
        #print(selectors)
        #print(len(selectors))
        crossover(selectors)
        mutation()

    print(averageTime)
    plt.plot(range(len(averageTime)),averageTime)
    plt.show()
if __name__ == '__main__':
    main()
